{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# _*Experiment with the Simon's Algorithm in Aqua*_\n",
    "\n",
    "This notebook demonstrates how to experiment with the `Simon`'s algorithm in `Qiskit Aqua`.\n",
    "\n",
    "We first import all necessary modules."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from qiskit import BasicAer\n",
    "from qiskit.aqua import QuantumInstance\n",
    "from qiskit.aqua.algorithms import Simon\n",
    "from qiskit.aqua.components.oracles import TruthTableOracle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [Simon's algorithm](https://en.wikipedia.org/wiki/Simon's_problem) is explained in more detail in the corresponding notebook located in the directory `algorithms`. We can experiment with it in Aqua by feeding it oracles created using truth tables. For example, we can create a `TruthTableOracle` instance as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "bitmaps = [\n",
    "    '01101001', \n",
    "    '10011001', \n",
    "    '01100110'\n",
    "]\n",
    "oracle = TruthTableOracle(bitmaps)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As shown, the truthtable is specified with three length-8 bitstrings, each containing the values of all entries for a particular output column in the table. Each bitstring has length $8$, so the truthtable has $3$ input bits; There are $3$ bitstrings, so the truthtable has $3$ output bits.\n",
    "\n",
    "The function $f$ represented by the truthtable is promised to be either 1-to-1 or 2-to-1. Our goal is to determine which. For the case of 2-to-1, we also need to compute the mask $\\mathbf{s}$, which satisfies $\\forall \\mathbf{x},\\mathbf{y}$: $\\mathbf{x} \\oplus \\mathbf{y} = \\mathbf{s}$ iff $f(\\mathbf{x}) = f(\\mathbf{y})$. Apparently, if $f$ is 1-to-1, the corresponding mask $\\mathbf{s} = \\mathbf{0}$.\n",
    "\n",
    "Let us first compute the groundtruth mask $\\mathbf{s}$ classically:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The groundtruth mask is 011.\n"
     ]
    }
   ],
   "source": [
    "def compute_mask(input_bitmaps):\n",
    "    vals = list(zip(*input_bitmaps))[::-1]\n",
    "    def find_pair():\n",
    "        for i in range(len(vals)):\n",
    "            for j in range(i + 1, len(vals)):\n",
    "                if vals[i] == vals[j]:\n",
    "                    return i, j\n",
    "        return 0, 0\n",
    "\n",
    "    k1, k2 = find_pair()\n",
    "    return np.binary_repr(k1 ^ k2, int(np.log2(len(input_bitmaps[0]))))\n",
    "\n",
    "mask = compute_mask(bitmaps)\n",
    "print(f'The groundtruth mask is {mask}.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we can create a `Simon` instance using the oracle, and run it to check the result against the groundtruth."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The mask computed using Simon is 011.\n"
     ]
    }
   ],
   "source": [
    "simon = Simon(oracle)\n",
    "backend = BasicAer.get_backend('qasm_simulator')\n",
    "result = simon.run(QuantumInstance(backend, shots=1024))\n",
    "print('The mask computed using Simon is {}.'.format(result['result']))\n",
    "assert(result['result'] == mask)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also quickly try a truthtable that represents a 1-to-1 function (i.e., the corresponding mask is $\\mathbf{0}$), as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The groundtruth mask is 000.\n",
      "The mask computed using Simon is 000.\n"
     ]
    }
   ],
   "source": [
    "bitmaps = [\n",
    "    '00011110', \n",
    "    '01100110', \n",
    "    '10101010'\n",
    "]\n",
    "mask = compute_mask(bitmaps)\n",
    "print(f'The groundtruth mask is {mask}.')\n",
    "oracle = TruthTableOracle(bitmaps)\n",
    "simon = Simon(oracle)\n",
    "result = simon.run(QuantumInstance(backend, shots=1024))\n",
    "print('The mask computed using Simon is {}.'.format(result['result']))\n",
    "assert(result['result'] == mask)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
